package com.bolins.math.heap;



/**
 * 堆结构(以int为例)
 * 
 * @author liuys
 * 
 */
public class Heap  {
	/**
	 * 堆数组
	 */
	private int[] heap;
	
	/**
	 * 堆数组长度
	 */
	private int length;
	
	/**
	 * 堆节点的数量
	 */
	private int heapSize;
	
	public Heap(int[] heap){
		this.heap = heap;
		length = heap.length;
		heapSize = heap.length;
		build();
	}
	
	/**
	 * 堆修改
	 * 
	 * 输入为一个数组input和下标i
	 * 
	 * 当input[i]小于其子女节点时，就要对堆进行修改，使其符全堆标准
	 * 
	 * 堆修改的前提条件是 下标为i的节点的左右两个子树是都是堆。
	 * 
	 * 伪代码：
	 * 		l <-- left(i);
	 * 		r <-- right(i);
	 * 		if l<=heap-size(heap) and heap[l]>heap[i]
	 * 			then max <-- l;
	 * 			else max <-- i;
	 * 		if r<=heap-size(heap) and heap[r]>heap[max]
	 * 			then max <-- r;
	 * 		if max != i
	 * 			then exchange heap[i] <--> heap[max];
	 * 				 modify(max);
	 * @param input
	 * @param i
	 */
	public void modify(int i) {
		if(heapSize<1)
			throw new RuntimeException("heap underflow.");
		
		int l = 2 * i, r = 2 * i+1, max = 0;
		
		if (l <= heapSize && heap[l-1] > heap[i-1]) {
			max = l;
		} else {
			max = i;
		}

		if (r <= heapSize && heap[r-1] > heap[max-1]) {
			max = r;
		}

		if (max != i) {
			int temp = heap[max-1];
			heap[max-1] = heap[i-1];
			heap[i-1] = temp;

			modify(max);
		}
	}
	
	/**
	 * 构建堆
	 * 
	 * 输入为一个随机数组
	 * 
	 * 子数组中input[n/2+1...n]都是堆中的叶子节点, 所以只需要对所有
	 * 非叶子节点做一次对堆修改即可
	 * 
	 * 因为叶子节点符合堆修改的前提条件。
	 * 
	 * 伪代码：
	 * 		heap-size[heap] <-- length(heap);
	 * 		for i <-- length[heap]/2 downto 1
	 * 			do modify(i);
	 * 
	 */
	public void build() {
		if(heapSize<1)
			throw new RuntimeException("heap underflow.");
		
		for (int i = length / 2; i >= 1; i--) {
			modify(i);
		}
	}

	/**
	 * 堆排序
	 * 
	 * 根据堆的特性，根节点是数组中最大的值，故每次将根取出，
	 * 再根据堆修改重新生成堆，再取出根....一直循环下去，
	 * 最后得到长升序的数组。
	 * 
	 * 输入为一个随机数组
	 * 
	 * 思路： 
	 * 		1、将随机数组构建成堆 
	 * 		2、将循环将根与最后一个叶子节点互换,并将堆的heap-size减1. 
	 * 		3、对根节点做堆修改
	 * 
	 * 伪代码：
	 * 		build();
	 * 		for i <-- length(heap) downto 2
	 * 			do exchange heap[1] <--> heap[i];
	 * 			   heap-size[heap] <-- heap-size[heap]-1;
	 * 			   modify(i);
	 */
	public int[] sort() {
		build();
		
		for(int i = length;i>1;i--){
			int temp = heap[0];
			heap[0] = heap[i-1];
			heap[i-1] = temp;
			heapSize--;
			modify(1);
		}
		return heap;
	}

	
	//----------以下是作为堆的扩展应用---优先级队列------
	
	/**
	 * 向优先队列中插入一个Key
	 * 
	 * 伪代码：
	 * 		heap-size[heap] <-- heap-size[heap]+1;
	 * 		i <-- heap-size[heap]
	 * 		while i>1 and heap[i]<key
	 * 			do heap[i] <-- heap[parent(i)];
	 * 			   i <-- parent(i);
	 * 		heap[i] <-- key;
	 */
	public void insert(int key){
		build();
		
		if(length==heapSize){
			length ++;
			int[] newHeap = new int[length];
			for(int i = 0;i<heapSize;i++){
				newHeap[i] = heap[i];
			}
			heap = newHeap;
		}
		
		heapSize++;
		int i = heapSize;
		while(i>1 && heap[i-1]<key){
			heap[i-1] = heap[i/2-1];
			i = i/2;
		}
		heap[i-1] = key;
	}
	
	/**
	 * 返回堆的根节点
	 * 
	 * @return
	 */
	public int maximun(){
		if(heapSize<1)
			throw new RuntimeException("heap underflow.");
		return heap[0];
	}
	
	/**
	 * 返回堆的根节点，并将根节点与堆的最后一个堆节点互换然后做堆修改操作
	 * 
	 * @return
	 */
	public int extractMax(){
		if(heapSize<1)
			throw new RuntimeException("heap underflow.");
		int max = heap[0];
		
		heap[0] = heap[heapSize-1];
		heapSize--;
		modify(1);
		
		return max;
	}
	
	public int[] getHeap(){
		return heap;
	}
}
